package zisu.algorithm.algorithm.MaxHeap;

//最大堆 堆顶 数值是最大的。
//todo
// 1.任务的优先级 可以分3个档次 每个档次的权重一样；；
// 2.当需要调整任务先后顺序的时候，如果向上调 那么把这个任务调整 为 目的任务的权重 +1；；
// 3.当需要调整任务先后顺序的时候，如果向下调 那么把这个任务调整 为 目的任务的权重 -1；；
// 4.因为 maxheap 的优势在于可以选举出 最大值（动态的），他并不可以通过遍历 整个数组的方式 得到顺序，但是可以把任务拿出来手动排序
public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data = new Array<>();
    }

    public int size(){
        return data.getSize();
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    //计算出 index 这个索引的父亲 是哪个节点。
    public int parent(int index){
        // parent(i) = (i - 1) / 2
        // left child (i) = 2*i + 1
        // right child (i) = 2*i + 2
        if(index == 0){
            throw new IllegalArgumentException("index = 0 ; 是没有父亲节点的");
        }
        return (index - 1) / 2;
    }

    //得到优先队列里面的所有 数据，但是不把这些数据取出。
    public int[] peekAll(){
        return null;
    }


    //返回 index 节点的左子树节点。
    public int leftChild(int index){
        return 2 * index + 1;
    }

    //返回 index 节点的右子树节点。
    public int rightChild(int index){
        return 2 * index + 2;
    }

    //向堆中添加元素
    public void add(E e){
        data.addLast(e);
        //data.getSize()-1 是新增 元素的位置
        siftUp(data.getSize()-1);
    }

    //形象的理解 就是上浮操作，如果新加入的这个节点 权重是比较大的，那么它就会像水中的气泡一样往上浮。
    private void siftUp(int i) {
        //1. i>0 非根节点；； 2. i的父亲节点的在值  比 i的值 小。
        while (i>0 && data.get(parent(i)).compareTo(data.get(i))<0){
            int parentIndex = parent(i);
            data.swap(i,parentIndex);
            i = parentIndex;
        }
    }

    //看堆中最大元素
    public E findMax(){
        if(data.getSize() == 0){
            throw new IllegalArgumentException("这个堆 现在为空");
        }
        return data.get(0);
    }

    //取出堆中最大元素
    public E extractMax(){
        E e = findMax();
        //之所以把 max值 和 最后一个元素交换的原因是 ；用siftDown 重新选举出一个根节点
        data.swap(0,data.getSize()-1);
        data.removeLast();
        siftDown(0);
        return e;
    }

    private void siftDown(int k) {
        // 当左孩子不存在的时候（数组越界了）
        while (leftChild(k) < data.getSize()){
            //j 表示左右子树中 最大值得索引。
            int j = leftChild(k);
            if(
                    // j+1 < data.getSize() 代表右子树存在。
                    j+1 < data.getSize()
                            //并且 右子树 大于 左子树
                            && data.get(j+1).compareTo(data.get(j))>0
            ) {
                //如果满足 上述两个条件，那么就存左子树的节点+1  切换到 右子树。
                j++;
            }
            if(data.get(k).compareTo(data.get(j))>=0){
                break;
            }
            data.swap(k,j);
            k = j;
        }
    }
}
